package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.ArrayProblem;
import cn.pugle.oj.catalog.MathProblem;

import java.util.Arrays;
import java.util.Random;

/**
 * https://leetcode.com/problems/random-pick-with-blacklist/
 *
 * @author tzp
 * @since 2020/9/29
 */
public class LC710 implements ArrayProblem, MathProblem {
    class Solution {
        int size;
        int[] blacklist;
        Random randomor;

        public Solution(int N, int[] blacklist) {
            Arrays.sort(blacklist);
            this.blacklist = blacklist;
            size = N - blacklist.length;
            randomor = new Random();
        }

        public int pick() {
            int i = randomor.nextInt(size);
            for (int j = 0; j < blacklist.length; j++) {
                if (i < blacklist[j]) {
                    return i;
                } else {
                    i = i + 1;
                }
            }
            return i;
        }
    }

    public static void main(String[] args) {
        LC710 lc710 = new LC710();
        Solution solution = lc710.new Solution(10, new int[]{3, 4, 7});
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
    }
}
